﻿#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using namespace std;

#include <vector>
// 双指针练习：移动零
class Solution1 {
public:
    void moveZeroes(vector<int>& nums) {
        int dest = -1;
        int cur = 0;
        for (int cur = 0; cur < nums.size(); cur++)
        {
            if (nums[cur] == 0)
                ;
            else
            {
                dest++;
                swap(nums[dest], nums[cur]);
            }
        }
    }
};
// 双指针练习：复写零
class Solution2 {
public:
    void duplicateZeros(vector<int>& arr) {
        int len = arr.size();
        int cur = 0, dest = -1;
        // 寻找cur的位置
        while (dest != len - 1)
        {
            if (arr[cur] != 0)
                dest++;
            else
                dest += 2;
            if (dest >= len - 1)
                break;
            cur++;
        }
        // 处理边界情况
        if (dest >= len)
        {
            arr[len - 1] = 0;
            cur--;
            dest -= 2;
        }
        // 从后往前移动覆盖
        while (cur >= 0)
        {
            if (arr[cur] != 0)
                arr[dest--] = arr[cur--];
            else
            {
                arr[dest] = arr[cur];
                dest--;
                arr[dest--] = arr[cur--];
            }
        }
    }
};

// 双指针练习：快乐数
class Solution3 {
public:
    // 返回 n 这个数每一位上的平方和 
    int bitSum(int n)
    {
        int sum = 0;
        while (n)
        {
            int x = n % 10;
            sum = x * x + sum;
            n = n / 10;
        }
        return sum;
    }

    bool isHappy(int n)
    {
        int slow = n;
        int fast = bitSum(n);
        while (slow != fast)
        {
            slow = bitSum(slow);
            fast = bitSum(bitSum(fast));
        }
        return slow == 1;
    }
};
// 双指针练习：盛水最多的容器
class Solution4 {
public:
    int maxArea(vector<int>& height)
    {
        int left = 0, right = height.size() - 1, ans = 0;
        while (left < right)
        {
            int v = min(height[left], height[right]) * (right - left);
            ans = max(ans, v);

            // 每次移动较短边
            if (height[left] < height[right])
                left++;
            else
                right--;
        }
        return ans;
    }
};
// 有效三角形的个数
#include <algorithm>
class Solution5 {
public:
    int triangleNumber(vector<int>& nums)
    {
        int sum = 0;
        sort(nums.begin(), nums.end());
        int c = nums.size() - 1;
        for (; c >= 2; c--)
        {
            int left = 0, right = c - 1;
            while (left < right)
            {
                if (nums[left] + nums[right] > nums[c])
                {
                    sum += right - left;
                    right--;
                }
                else
                    left++;
            }
        }
        return sum;
    }
};

//int main()
//{
//    Solution s;
//    vector<int> v = { 2,2,3,4 };
//    s.triangleNumber(v);
//    return 0;
//}

// 双指针 - 和为s的两个数字
class Solution6 {
public:
    vector<int> FindNumbersWithSum(const vector<int>& a, int sum)
    {
        int len = a.size(), left = 0, right = len - 1;
        while (left < right)
        {
            if (a[left] + a[right] > sum)
                right--;
            else if (a[left] + a[right] < sum)
                left++;
            else
                return { a[left], a[right] };
        }
    }
};
// 双指针 - 三数之和 
class Solution7 {
public:
    vector<vector<int>> threeSum(vector<int>& nums)
    {
        int n = nums.size();
        // 排序
        sort(nums.begin(), nums.end());

        vector<vector<int>> v;
        for (int i = 0; i < n;)
        {
            int left = i + 1, right = n - 1;
            int target = -nums[i];
            // 双指针算法
            while (left < right)
            {
                if (nums[left] + nums[right] > target)
                    right--;
                else if (nums[left] + nums[right] < target)
                    left++;
                else
                {
                    // 直接push_back，用花括号初始化
                    v.push_back({ nums[i], nums[left], nums[right] });
                    left++;
                    right--;
                    // 去重left  right
                    while (left < right && nums[left] == nums[left - 1])
                        left++;
                    while (left < right && nums[right] == nums[right] + 1)
                        right--;
                }
            }
            i++;
            // 去重 i
            while (i < n && nums[i] == nums[i - 1])
                i++;
        }
        return v;
    }
};
// 双指针 - 四数之和 
class Solution8 {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target)
    {
        int n = nums.size();
        sort(nums.begin(), nums.end());

        vector<vector<int>> v;

        for (int begin = 0; begin < n;)
        {
            // 三数之和
            for (int i = begin + 1; i < n;)
            {
                int left = i + 1, right = n - 1;
                while (left < right)
                {
                    // 使用long long防止整形溢出
                    long long sum = nums[begin] + nums[i];
                    long long add = nums[left] + nums[right];
                    if (sum + add > (long long)target)
                        right--;
                    else if (sum + add < (long long)target)
                        left++;
                    else
                    {
                        v.push_back({ nums[begin], nums[i], nums[left], nums[right] });
                        left++;
                        right--;
                        // 去重left right
                        while (left < right && nums[left] == nums[left - 1])
                            left++;
                        while (left < right && nums[right] == nums[right + 1])
                            right--;
                    }
                }
                // 去重 i
                i++;
                while (i < n && nums[i] == nums[i - 1])
                    i++;
            }
            // 去重 begin
            begin++;
            while (begin < n && nums[begin] == nums[begin - 1])
                begin++;
        }
        return v;
    }
};

// 滑动窗口 - 长度最小的子数组
class Solution9 {
public:
    int minSubArrayLen(int target, vector<int>& nums)
    {
        int len = nums.size();
        int ret = INT_MAX, sum = 0;
        for (int left = 0, right = 0; right < len; right++)
        {
            sum += nums[right];                     
            while (sum >= target)
            {
                ret = min(ret, right - left + 1);   // 循环判断最小值
                sum -= nums[left++];                // 出窗口
            }
        }
        return ret == INT_MAX ? 0 : ret;
    }
};

// 滑动窗口 - 无重复字符的最长子串
class Solution0 {
public:
    int lengthOfLongestSubstring(string s)
    {
        int hash[128] = { 0 };
        int dest = 0, cur = 0, len = s.size();
        int ret = 0;
        while (cur < len)
        {
            hash[s[cur]]++;
            while (hash[s[cur]] > 1)
            {
                hash[s[dest]]--;
                dest++;
            }
            ret = max(ret, cur - dest + 1);
            cur++;
        }
        return ret;
    }
};
class Solution11 {
public:
    int lengthOfLongestSubstring(string s)
    {
        int len = s.size(), ret = 0;
        int hash[128] = { 0 };
        for (int left = 0, right = 0; right < len; right++)
        {
            hash[s[right]]++;// 进窗口
            while (hash[s[right]] > 1)
            {
                hash[s[left]]--;    // 出窗口
                left++;
            }
            ret = max(ret, right - left + 1);// 更新结果
        }
        return ret;
    }
};

class Solution12 {
public:
    int longestOnes(vector<int>& nums, int k) {
        int n = nums.size();
        int left = 0, lsum = 0, rsum = 0;
        int ans = 0;
        for (int right = 0; right < n; ++right) {
            rsum += 1 - nums[right];
            while (lsum < rsum - k) {
                lsum += 1 - nums[left];
                ++left;
            }
            ans = max(ans, right - left + 1);
        }
        return ans;
    }
};
// 暴力枚举+双指针
class Solution13 {
public:
    int longestOnes(vector<int>& nums, int k)
    {
        int len = nums.size();

        int ans = 0;
        for (int left = 0; left < len; left++)
        {
            int ret = 0, cnt = 0;
            for (int right = left; right < len; right++)
            {
                if (nums[right] == 0)
                    cnt++;
                if (cnt > k)
                    break;
                ret += 1;
            }
            ans = max(ans, ret);
        }
        return ans;
    }
};
// 滑动窗口 - 最大连续 1 的个数III
class Solution14 {
public:
    int longestOnes(vector<int>& nums, int k)
    {
        int len = nums.size();
        int cnt = 0, ans = 0;
        for (int left = 0, right = 0; right < len; right++)
        {
            // 进窗口
            if (nums[right] == 0)
                cnt++;
            // 循环判断
            while (cnt > k)
            {
                // 出窗口
                if (nums[left] == 0)
                    cnt--;
                left++;
            }
            // 更新结果
            ans = max(ans, right - left + 1);
        }
        return ans;
    }
};
int mainx()
{
    Solution14 s;
    vector<int> v = { 1,1,1,0,0,0,1,1,1,1,0 };
    int ret = s.longestOnes(v, 2);
    return 0;
}
// 暴力解法
class Solution16 {
public:
    int minOperations(vector<int>& nums, int x)
    {
        int sum = 0, len = nums.size();
        for (auto e : nums)
            sum += e;
        int target = sum - x, ans = -1;
        if (target < 0)
            return -1;
        for (int left = 0; left < len; left++)
        {
            int add = 0;
            for (int right = left; right < len; right++)
            {
                add += nums[right];
                if (add > target)
                    break;
                if (add == target)
                    ans = max(ans, right - left + 1);
            }
        }
        if (ans == -1)
            return -1;
        else
            return len - ans;
    }
};

int maina()
{
    //Solution s;
    //vector<int> v = { 3,2,20,1,1,3 };
    //s.minOperations(v, 10);
    return 0;
}
// 滑动窗口 - 将 x 减到 0 的最⼩操作数
class Solution15 {
public:
    int minOperations(vector<int>& nums, int x)
    {
        int len = nums.size(), sum = 0;
        for (int i = 0; i < len; i++)
            sum += nums[i];
        int target = sum - x, ans = -1;
        if (target < 0)
            return -1;
        for (int left = 0, right = 0, add = 0; right < len; right++)
        {
            add += nums[right];
            while (add > target)
            {
                add -= nums[left];
                left++;
            }
            if (add == target)
                ans = max(ans, right - left + 1);
        }
        if (ans != -1)
            return len - ans;
        else
            return -1;
    }
};
#include<unordered_map>
class Solution00
{
public:
    int totalFruit(vector<int>& f)
    {
        unordered_map<int, int> hash; // 统计窗⼝内出现了多少种⽔果
        int ret = 0;
        for (int left = 0, right = 0; right < f.size(); right++)
        {
            hash[f[right]]++; // 进窗⼝
            while (hash.size() > 2) // 判断
            {
                // 出窗⼝
                hash[f[left]]--;
                if (hash[f[left]] == 0)
                    hash.erase(f[left]);
                left++;
            }
            ret = max(ret, right - left + 1);
        }
        return ret;
    }
};

class Solutionc {
public:
    bool isEqual(unordered_map<int, int>& hash1, unordered_map<int, int>& hash2)
    {
        if (hash1.size() != hash2.size()) return false;

        for (const auto& e : hash1)
        {
            unordered_map<int, int>::iterator it = hash2.find(e.first);
            if (it == hash2.end() || it->second != e.second)  return false;
        }
        return true;
    }
    vector<int> findAnagrams(string s, string p)
    {
        vector<int> v;
        unordered_map<int, int> hash1, hash2;
        for (const auto& e : p)
            hash1[p[e - 'a']]++; //p的哈希

        int lenp = p.size(), lens = s.size();

        for (int left = 0; left < lens; left++)
        {
            for (int right = left; right < lenp; right++)
            {
                hash2[s[right] - 'a']++;
            }
            if (isEqual(hash1, hash2))
                v.push_back(left);
            hash2.clear();
        }
        return v;
    }
};

class Solutionm {
public:
    // 比较数组是否相等
    bool compare_arrays(int arr1[], int arr2[], int size)
    {
        for (int i = 0; i < size; i++) {
            if (arr1[i] != arr2[i]) {
                return false;
            }
        }
        return true;
    }

    vector<int> findAnagrams(string s, string p)
    {
        vector<int> v;
        int hash1[6] = { 0 };
        for (auto e : p)     //统计p中各字符的个数
            hash1[e - 'a']++;

        int lens = s.size(), lenp = p.size();
        int hash2[6] = { 0 };
        for (int left = 0, right = 0; right < lens; right++)
        {
            int in = s[right];
            hash2[in - 'a']++;        //进窗口
            if (right - left + 1 > lenp) //循环判断
            {
                int out = s[left];
                hash2[out - 'a']--;   //出窗口
                left++;
            }
            if (compare_arrays(hash1, hash2, 6))
                v.push_back(left);
        }
        return v;
    }
};
//int main()
//{
//    Solution s;
//    string s1 = "acdcaeccde";
//    string p = "c";
//    s.findAnagrams(s1, p);
//    return 0;
//}
// 滑动窗口 - 找到字符串中所有字⺟异位词
class Solutionx {
public:
    vector<int> findAnagrams(string s, string p)
    {
        vector<int> v;
        int hash1[26] = { 0 };
        for (auto e : p)
            hash1[e - 'a']++; //p的哈希

        int hash2[26] = { 0 };
        int lenp = p.size(), lens = s.size();

        for (int left = 0, right = 0, count = 0; right < lens; right++)
        {
            char in = s[right];
            hash2[in - 'a']++;  //进窗口
            if (hash2[in - 'a'] <= hash1[in - 'a']) count++; //维护count

            if (right - left + 1 > lenp)
            {
                char out = s[left++];
                if (hash2[out - 'a'] <= hash1[out - 'a']) count--;
                hash2[out - 'a']--; //count--
            }
            if (count == lenp)
                v.push_back(left);
        }
        return v;
    }
};
// 滑动窗口 - 串联所有单词的⼦串
class Solutionl {
public:
    vector<int> findSubstring(string s, vector<string>& words)
    {
        vector<int> v;
        unordered_map<string, int> hash1;
        for (auto e : words)
            hash1[e]++;         // 把words中的每个串都放到hash1里

        int len = words[0].size();  // 每个字符的长度
        int lens = s.size(), lenw = words.size();
        for (int i = 0; i < len; i++)  // 循环word中字符串的长度次
        {
            unordered_map<string, int> hash2;
            for (int left = i, right = i, count = 0; right + len <= lens; right += len)
            {
                string in = s.substr(right, len);       // 截取len个字符串的长度
                hash2[in]++;                            // 进窗口
                if (hash2[in] <= hash1[in])  count++;    // 维护count

                if (right - left + 1 > len * lenw)
                {
                    string out = s.substr(left, len);
                    if (hash2[out] <= hash1[out])    count--;
                    hash2[out]--;                       // 出窗口
                    left += len;
                }

                if (count == lenw)                       // 
                    v.push_back(left);
            }
        }
        return v;
    }
};

// 滑动窗口 - 最⼩覆盖⼦串
class Solutionp {
public:
    string minWindow(string s, string t)
    {
        int hash1[128] = { 0 };
        int kinds = 0;
        for (auto e : t)
        {
            if (hash1[e] == 0)   kinds++;
            hash1[e]++;
        }

        int lens = s.size(), lent = t.size();
        int hash2[128] = { 0 };
        int minlen = INT_MAX, begin = -1;
        for (int left = 0, right = 0, count = 0; right < lens; right++)
        {
            hash2[s[right]]++;              //进窗口
            if (hash2[s[right]] == hash1[s[right]])  count++;
            while (count == kinds)
            {
                if (right - left + 1 < minlen)
                {
                    minlen = right - left + 1;
                    begin = left;
                }
                char out = s[left++];
                if (hash2[out] == hash1[out])  count--;
                hash2[out]--;
            }
        }
        if (begin == -1) return "";
        else    return s.substr(begin, minlen);
    }
};